package com.sx.sx1.lintcode.day717;

public class LC792 {

    static class Solution {
        /**
         * @param n: the number
         * @return: the rank of the number
         */
        public int kthPrime(int n) {
            int ans =0;
            for (int i = 2; i <=n ; i++) {
                //判断是否是质数
                if(f(i)){
                    ans++;
                }
            }

            return ans;
        }

        public boolean f(int x){
            if(x==2 || x==3) return true;
            //不在6的倍数的2侧肯定不是质数
            if(x%6!=1 && x%6!=5) return false;
            int sqrt=(int)Math.sqrt(x);
            for (int i = 5; i <=sqrt ; i+=6) {
                //在6的倍数2侧也可能不是质数
                if(x%i==0 || x%(i+2) ==0) return false;
            }

            return true;
        }
    }

    public static void main(String[] args) {
        Solution obj = new Solution();
        System.out.println(obj.kthPrime(3)); //2
        System.out.println(obj.kthPrime(11)); //5
    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
您有215条未读消息，请及时查看
792 · 第K个质数
算法
简单
通过率
49%

题目
题解19
笔记
讨论36
排名
记录
描述
给出质数n，输出它是第几个质数。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


n <= 100000。
质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。
样例
样例1

输入: n = 3
输出: 2
解释:
[2,3,5]，3是第2个质数。
样例2

输入: n = 11
输出: 5
解释:
[2,3,5,7,11]，11是第五个质数。
标签
相关题目

235
分解质因数
简单
推荐课程

春招算法高频题冲刺班
精准押题，抱佛脚突击算法面试，最近6个月新题/难题/高频题全覆盖！
已开启智能提示
发起考试
15 分 00 秒
123456789

控制台
        历史提交

 */
